/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    /**
     * 1,  2, 3, 4, 5
     * p1  p2 交换
     * 1   3  2  4 5
     * p1   p2 前进
     * 1   3  2  4 5
     * p1   p2 交换
     * 1   3  5  4 2
     * p1 p2 交换
     *
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        ListNode oddHead = new ListNode(-1);
        ListNode evenHead = new ListNode(-1);
        ListNode evenP = evenHead;
        ListNode oddP = oddHead;
        boolean isOdd = true;
        while (head != null) {
            if (isOdd) {
                oddP.next = head;
                oddP = head;
            } else {
                evenP.next = head;
                evenP = head;
            }
            head = head.next;
            isOdd = !isOdd;
        }
        evenP.next = null;
        oddP.next = null;
        oddP.next = evenHead.next;
        return oddHead.next;
    }

    public static void main(String[] args) {
        ListNode oddHead = createList(new int[]{1});
        Solution solution = new Solution();
        ListNode head = solution.oddEvenList(oddHead);
    }

    public static ListNode createList(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        ListNode head = new ListNode(array[0]);
        ListNode pre = head;
        for (int i = 1; i < array.length; i++) {
            ListNode listNode = new ListNode(array[i]);
            pre.next = listNode;
            pre = listNode;
        }
        return head;
    }
}